package 中等.找规律;

/**
 * 神奇字符串 s 仅由 '1' 和 '2' 组成，并需要遵守下面的规则：
 * 神奇字符串 s 的神奇之处在于，串联字符串中 '1' 和 '2' 的连续
 * 出现次数可以生成该字符串。
 * s 的前几个元素是 s = "1221121221221121122……" 。如果将 s 中
 * 连续的若干 1 和 2 进行分组，可以得到 "1 22 11 2 1 22 1 22
 * 11 2 11 22 ......" 。每组中 1 或者 2 的出现次数分别是 "1 2
 * 2 1 1 2 1 2 2 1 2 2 ......" 。上面的出现次数正是 s 自身。
 * 给你一个整数 n ，返回在神奇字符串 s 的前 n 个数字中 1 的数目。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/magical-string
 */
public class 神奇字符串_481 {

    public static void main(String[] args) {

        System.out.println(magicalString(4));

    }

    /**
     * 找规律：
     * 观察神奇字符串，发现 1 和 2 永远都会交替出现，1 可能是 1 也可能是 11
     * 2 可能是 2 也可能是 22
     * 定义两个指针 pre cur
     * 1   2   2     _
     * *      pre   cur
     * cur 的数字由前一个数字决定，和前一个数字相反
     * cur 的数字数量由 pre 指针所在的数字决定
     * 每次指针移到，pre++ ，cur+=n.charAt(pre)
     *
     * @param n
     * @return
     */
    public static int magicalString(int n) {
        if (n <= 3) {
            return 1;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        dp[2] = 2;

        int pre = 2, cur = 3;
        while (cur < dp.length) {
            dp[cur] = 3 - dp[cur - 1];
            cur++;
            if (dp[pre] == 2 && cur < dp.length) {
                dp[cur] = dp[cur - 1];
                cur++;
            }
            pre++;
        }
        int count = 0;
        for (int num : dp) {
            count += (2 - num);
        }
        return count;
    }

}
